
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static struct timespec time_start, time_end;

void start_time()
{
    clock_gettime(CLOCK_MONOTONIC_RAW, &time_start);
}

void end_time()
{
    clock_gettime(CLOCK_MONOTONIC_RAW, &time_end);
}

long delta_time()
{
    return (time_end.tv_sec - time_start.tv_sec) * 1000000000 + (time_end.tv_nsec - time_start.tv_nsec);
}

static int word = sizeof(char*); // 每个存储字大小
static int line = 512 / sizeof(char*); // 每个cache line字数
static int page = 4096; // 每个页面大小， 字节数

void borken_order_loop_list_simple(char** buf, int max_col, int max_row, long iter_count)
{
    int i, j;
    int ni, nj;
    int cur, next;
    for (i = 0; i < max_row; i++) {
        for (j = 0; j < max_col; j++) {
            if (i + 1 == max_row) {
                ni = 0;
                nj = (j + 1) % max_col;
                // next = 0 + (j + 1) % max_col;
            } else {
                ni = i + 1;
                nj = (i + j) % max_col;
                // next = (i + 1) * max_col + (i + j) % max_col;
            }
            cur = i * max_col + j;
            next = ni * max_col + nj;
            // printf("i:j %d:%d -> ni:nj, %d:%d, max %d:%d\n", i, j, ni, nj, max_row, max_col);
            *(buf + cur) = (char*)(buf + next);
            // printf("%d, %p => %d, %p; =%p\n", cur, buf + cur, next, buf + next, *(buf + cur));
        }
    }
}

void borken_order_loop_list_fast(char** buf, int max_col, int max_row, long iter_count)
{
    int i, j;
    int ni, nj;
    int cur, next;
    int n = 0;
    int max_iter = max_row * max_col;
    for (i = j = 0; n < max_iter && n < iter_count + 2; n++) {
        if (i + 1 == max_row) {
            ni = 0;
            nj = (j + 1) % max_col;
            // next = 0 + (j + 1) % max_col;
        } else {
            ni = i + 1;
            nj = (i + j) % max_col;
            // next = (i + 1) * max_col + (i + j) % max_col;
        }
        cur = i * max_col + j;
        next = ni * max_col + nj;
        // printf("i:j %d:%d -> ni:nj, %d:%d, max %d:%d\n", i, j, ni, nj, max_row, max_col);
        *(buf + cur) = (char*)(buf + next);
        // printf("%d, %p => %d, %p; =%p\n", cur, buf + cur, next, buf + next, *(buf + cur));
        i = ni;
        j = nj;
    }
}

int buf_init(char** buf, long size, long iter_count)
{
    // 当size小于一个page时， buf基地址必须cache line字节数对齐， 且必须是整数倍
    // 当size大于一个page时， buf基地址必须一个page对齐， 且必须是整数倍
    int max_col, max_row;

    if (size < line) {
        printf("Error\n");
        //error
        return 1;
    }
    if (size < page * 2) {
        if (size % line) {
            printf("Error: not align line\n");
            return 2;
        }
        max_col = line / word;
        max_row = size / line;
    } else if (size >= page * 2) {
        // 这里使用page作为block块步进，这个是最好的方式让cache失效吗？
        max_col = page / word;
        max_row = size / page;

        if (size % page) {
            printf("Warn: not align page %ld\n", size);
            // long block_size = 2048;
            // max_col = block_size / word;
            // max_row = size / block_size;
            // return;
        }
    } else {
        printf("Error, are kid me?\n");
    }

    // 构造乱序循环列表，这个乱序构造目的在于排除cache影响，以达到测试出真正mem延迟
    // 当前将整个分配的内存看作一个二维表，每单元格为一个word，一行有block_size/word, 其中block_size为预估的cache line大小或一个page大小，共有size/block_size行
    // 上一行的一个的单元格存放相邻下一行（如果当前为最后一行，则为第0行）的某个单元格的地址指针
    // 将整个表格初始化完成之后就变成一个完整的循环队列
    // 其中映射下一行的地址算法相当程度决定了cache失效的程度
    // borken_order_loop_list_simple(buf, max_col, max_row, iter_count);
    borken_order_loop_list_fast(buf, max_col, max_row, iter_count);

    // #define DEBUG_TEST
#ifdef DEBUG_TEST
    char* sbuf[4];
    max_col = 2;
    max_row = 2;
    buf = sbuf;
    printf("*******test borken_order_loop_list init  *********\n");
    for (int i = 0; i < max_row; i++) {
        for (int j = 0; j < max_col; j++) {
            printf("%p ", buf + j + i * max_row);
        }
        printf("\n");
    }
    bzero(buf, sizeof(char*) * 4);
    borken_order_loop_list_simple(buf, max_col, max_row, iter_count);
    printf("*******borken_order_loop_list_simple result*********\n");
    for (int i = 0; i < max_row; i++) {
        for (int j = 0; j < max_col; j++) {
            printf("%p ", *((char**)(buf + j + i * max_row)));
        }
        printf("\n");
    }
    bzero(buf, sizeof(char*) * 4);
    borken_order_loop_list_fast(buf, max_col, max_row, iter_count);
    printf("*******borken_order_loop_list_fast result*********\n");
    for (int i = 0; i < max_row; i++) {
        for (int j = 0; j < max_col; j++) {
            printf("%p ", *((char**)(buf + j + i * max_row)));
        }
        printf("\n");
    }
#endif

    return 0;
}

#define ONE p = (char**)*p
#define FIVE \
    ONE;     \
    ONE;     \
    ONE;     \
    ONE;     \
    ONE
#define TEN \
    FIVE;   \
    FIVE
#define HUNDRID \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN;        \
    TEN
#define COUNT_PER_ITER 100

// 这个很关键，如果没有这个编译器有可能将这个优化掉
char** broken_bb_p;
char** iterator_buf(char** p, long count)
{
    while (count--) {
        HUNDRID;
    }
    broken_bb_p = p; // 这一行很重要，没有这一行整个都可能不起作用
    return p;
}

void start_test(long buf_size)
{
    // long buf_size = (line * n_line * sizeof(char*));

    char** buf = malloc(buf_size + page);
    if (buf == NULL) {
        perror("Error, alloc mem: ");
        return;
    }

    char** p = buf;
    // 对齐
    if ((unsigned long)buf % page) {
        p = (char**)(page - (unsigned long)buf % page + (unsigned long)buf);
    }

    long count = 10000;
    long loop_n = 1;
    start_time();
    if (buf_init(p, buf_size, count * loop_n * COUNT_PER_ITER)) {
        return;
    }
    end_time();
    printf("init   time: %ld\n", delta_time());

    long ns;
    for (int i = 0; i < loop_n; i++) {
        start_time();
        p = iterator_buf(p, count);
        end_time();
        ns = delta_time();
    }
    printf("result time: %ld: %ld, %.4f, %.4fMB\n", ns, count, (double)ns / (double)count / COUNT_PER_ITER, buf_size / 1024. / 1024.);
    free(buf);
}

void usage(const char* argv[])
{
    printf("usage: %s buf_size\n", argv[0]);
    printf("     buf_size is number of KB\n");
}

int main(int argc, char const* argv[])
{
    start_test(1024 * 1024 * 384); // 这个值在笔记本上基本就可以测试出来了
    return 0;

    // // start_test(4096 * 10);
    // for (unsigned long i = 128; i <= 1024 * 1024 * 1124;) {
    //     // printf("size: %.4fKB\n", i / 1024.);
    //     start_test(i);

    //     if (i < 1024) {
    //         i += i;
    //     } else if (i < 4 * 1024) {
    //         i += 1024;
    //     } else {
    //         long s;
    //         for (s = 32 * 1024; s < i; s += s)
    //             ;
    //         i += s / 16;
    //     }
    //     // i = i + (i % (1024 * 64));
    // }
    // return 0;
}
